package offerbook;

import java.util.Arrays;

/**
 * @date 2019/11/11 0011 下午 6:02
 * 中位数：奇数是中间，偶数是两个均值
 *
 * 1：找出某堆数据中的中位数
 *
 * 2：找出某数据流中的中位数
 *  使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
 *
 * 使用partition，时间O(n),但是得存储数据。当有海量数据，不合适。
 * 使用堆，时间O(nlogn)
 *
 * 方式2：使用堆。可以源源不断读取数据流。
 */
public class Code64_GetMedian2 {


    public static Double getMedian(int[]arr) {
        if(arr == null || arr.length ==0){
            return 0d;
        }
        /**
         * 使用partition获得位置，当数据长度为n，
         * 要找的索引就是 (n-1)/2 ,也就是第(n-1)/2+1小的数
         */
        System.out.println("targetIndex = " + (arr.length-1)/2);
        int index = selectIndex(arr,0,arr.length-1,(arr.length-1)/2);
        System.out.println("index = " + index);

        if((arr.length & 1) ==0){
            //偶数
            int arrIndex = arr[index];
            index = selectIndex(arr,0,arr.length-1,(arr.length-1)/2+1);
            System.out.println("index1 = " + index);
            System.out.println(Arrays.toString(arr));
            return  ((double)(arrIndex+arr[index])) / 2;
        }
        //如果是奇数
        System.out.println(Arrays.toString(arr));
        return (double)arr[index];
    }

    private static int selectIndex(int[] arr, int begin,int end,int k) {
        if(arr== null || arr.length ==0){
            return -1;
        }
        int[] index = partition(arr,begin,end);
        if(k>= index[0] && k<=index[1]){
            return index[0];
        //继续往左partition
        }else if(k < index[0]){
            return selectIndex(arr,begin,index[0]-1,k);
        }else {
            //往右partition
            return selectIndex(arr,index[1]+1,end,k);
        }

    }

    private static int[] partition(int[] arr, int begin, int end) {
        //target,产生的索引是 begin~ end
        int target = arr[(int) (begin+Math.random()*(end - begin +1))];
        int less = begin-1;
        int more = end +1;
        int cur = begin;
        while (cur<more){
            if(arr[cur] < target){
                swap(arr,++less,cur++);
            }else if(arr[cur] > target){
                swap(arr,--more,cur);
            }else {
                cur++;
            }
        }
        return new int[]{less+1,more-1};
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int []arr = {5,6,7,8,9,10,1,2,3,4};
        System.out.println(getMedian(arr));
    }

}
